package arithmetic.leetcode;

import java.util.*;

/**
 * 二叉树的遍历
 *  DFS深度优先:--递归/栈实现
 *      中序遍历:先遍历左子树，反问根节点，遍历右子树
 *      前序遍历:先访问父节点，然后遍历左子树，最后遍历右子树
 *      后序遍历:先遍历左子树，再遍历右子树，最后反问根节点
 *  BFS广度优先:--借助队列来实现
 *      层序遍历:
 *
 * @author zhangzg
 * @date 2022/11/16
 */
class Tree {

    public static void main(String[] args) {
        Deque<Integer> stack = new LinkedList<>();
    }

    public List<Integer> inorderTraversalWhile(TreeNode root) {
        List<Integer> list=new ArrayList<>();
        Deque<TreeNode> stack=new LinkedList<>();
        while(root != null || !stack.isEmpty()){
            while(root!=null){
                stack.push(root);
                root=root.left;
            }
            root=stack.pop();
            list.add(root.val);
            root=root.right;
        }
        return list;
    }

    /**
     * 二叉树的中序遍历 -左 根 右
     * @param root
     * @return
     */
    public List<Integer> inorderTraversal(TreeNode root){
        List<Integer> list = new ArrayList<>();
        recursiveMidTree(root,list);
        return list;
    }

    /**
     * 中序遍历 左 根 右
     */
    public void recursiveMidTree(TreeNode root,List<Integer> list){
        if(root == null){
            return;
        }
        recursiveMidTree(root.left,list);
        list.add(root.val);
        recursiveMidTree(root.right,list);
    }

    /**
     * 前序遍历
     */
    public void recursiveBeforeTree(TreeNode root,List<Integer> list){
        if(root == null){
            return;
        }
        list.add(root.val);
        recursiveBeforeTree(root.left,list);
        recursiveBeforeTree(root.right,list);
    }

    /**
     * 后序遍历
     */
    public void recursiveAfterTree(TreeNode root,List<Integer> list){
        if(root == null){
            return;
        }
        recursiveAfterTree(root.left,list);
        recursiveAfterTree(root.right,list);
        list.add(root.val);
    }

    /**
     * Leetcode-102
     * 二叉树的层序遍历
     *  1、基于队列的实现
     *  2、递归实现
     *
     */
    //基于队列的实现
    public List<List<Integer>> levelOrder1(TreeNode root){
        Queue<TreeNode> queue = new LinkedList<>();
        List<List<Integer>> result = new LinkedList<>();
        if (root == null) return result;
        //将根节点入队
        queue.offer(root);
        while (!queue.isEmpty()){
            //获得每层的节点数
            int size = queue.size();
            //每层的结果集
            List<Integer> subList = new LinkedList<Integer>();
            //处理本层的节点-包括输出节点值和将节点的左右子树入队
            for (int i =0; i < size; i++){
                if (queue.peek().left != null) queue.offer(queue.peek().left);
                if (queue.peek().right != null) queue.offer(queue.peek().right);
                subList.add(queue.poll().val);
            }
            result.add(subList);
        }
        return result;
    }
    //基于递归的实现
    public List<List<Integer>> levelOrder(TreeNode root){
        List<List<Integer>> result = new LinkedList<>();
        levelPreVisit(result, root, 0);
        return result;
    }

    private void levelPreVisit(List<List<Integer>> result, TreeNode root, int height) {
        if (root == null) return;
        //新的层需要增加新的子list
        if (height >= result.size()){
            result.add(new LinkedList<Integer>());
        }
        //对当前节点的处理需要注意所在的层
        result.get(height).add(root.val);
        levelPreVisit(result, root.left, height+1);
        levelPreVisit(result, root.right, height+1);
    }

    /**
     * LeetCode-110 平衡二叉树
     * 给定一个二叉树，判断它是否是高度平衡的二叉树
     * 高度平衡二叉树定义:一个二叉树每个节点的左右两个子树的高度差的绝对值不超过1
     * 递归
     */
    public static boolean isBalanced(TreeNode root){
        if (root == null) {
            return true;
        }
        return helper(root) != -1;
    }

    private static int helper(TreeNode root) {
        if (root == null){
            return 0;
        }
        int left = helper(root.left);
        int right = helper(root.right);
        if(left == -1 || right == -1 || Math.abs(left - right) > 1){
            return -1;
        }
        return Math.max(left,right) + 1;
    }

    /**
     * LeetCode - 98
     * 验证二叉搜索树
     * 给你一个二叉树的根节点root,判断其是否是一个有效的二叉搜索树
     *  定义：节点的左子树只包含小于当前节点的树,节点的右子树只包含大于当前节点的数
     *      所有左子树和右子树自身必须也是二叉搜索树。
     *
     *  还可以基于中序遍历,如果满足二叉搜索树，那么返回的一定是由小到大的
     */
    public static boolean isValidBST(TreeNode root){
        return isValid(root, Long.MIN_VALUE, Long.MAX_VALUE);
    }
    public static boolean isValid(TreeNode root, long minValue, long maxValue) {
        if (root == null) return true;
        if (root.val >= maxValue || root.val <= minValue) return false;
        return isValid(root.left, minValue, root.val) && isValid(root.right, root.val, maxValue);
    }


    /**
     * LeetCode-437 路径总和
     * 给定一个二叉树的根节点root,和一个整数targetSum,求该二叉树里节点值之和等于targetSum的路径的数目。
     * 路径不需要从根节点开始,也不需要在叶子节点结束,但是路径方向必须是向下的。
     *
     * 前缀和的概念---
     *  map的key就是前缀和,value记录的是前缀和出现的次数
     *  初始化,任何节点本身也可以形成一个路径
     *  如果某个节点的值就是target,那么它本身就是一个解。
     */

    public static int pathSum(TreeNode root, int target){
        Map<Integer, Integer> prefixSum = new HashMap<>();
        prefixSum.put(0,1);
        return traversal(root,0,target,prefixSum);
    }
    private static int traversal(TreeNode root, int currSum,
                                 int target,
                                 Map<Integer, Integer> prefixSum) {
        if(root == null){
            return 0;
        }
        //记录当前节点的前缀和
        currSum = currSum + root.val;
        //差值 = 当前节点的前缀和-target
        int result = prefixSum.getOrDefault(currSum - target , 0);
        //将当前节点的前缀和放入Map,如果存在路径 + 1,没有这个前缀和的初始value为1
        prefixSum.put(currSum,prefixSum.getOrDefault(currSum, 0) + 1);
        result = result + traversal(root.left, currSum, target, prefixSum) +
                traversal(root.right, currSum, target, prefixSum);
        //一个节点的前缀和信息更新到Map时,它应当只对其子节点有效.所以往上层返回需要减1
        prefixSum.put(currSum, prefixSum.get(currSum) - 1);
        return result;
    }

    /**LeetCode-543
     * 二叉树的直径
     * 给定一课二叉树,你需要计算它的直径长度。一颗二叉树的直径长度时任意两个结点路径长度中的最大值。
     * 这条路径可能穿过也可能不穿过根节点
     */
    static int max = 0;
    public static int diameterOfBinaryTree(TreeNode root){
        maxDepth(root);
        return max;
    }
    private static int maxDepth(TreeNode node) {
        if (node == null) return 0;
        int left = maxDepth(node.left);
        int right = maxDepth(node.right);
        max = Math.max(max , left + right);
        return Math.max(left,right) + 1;
    }

    /**
     * Leetcode - 124
     * 二叉树的最大路径和
     * 路径：定义一条从树中任意节点出发,沿父节点-子节点连接,达到任意节点的序列。
     * 同一个节点在一条路径序列中至多出现一次。该路径至少包含一个节点。
     * 路径和:路径中各节点值的总和。
     * 给你一个二叉树的根节点root.返回其最大路径和。
     *
     * 实现逻辑:计算左子树和右子树的路径和最大值
     */
    static int maxValue = Integer.MIN_VALUE;
    public static int maxPathSum(TreeNode root){
        maxPathDown(root);
        return maxValue;
    }
    private static int maxPathDown(TreeNode node) {
        if (node == null) return 0;
        int left = Math.max(0, maxPathDown(node.left));
        int right = Math.max(0, maxPathDown(node.right));
        //取已有最大值以及当前节点值和左右子树节点值的和进行比较
        maxValue = Math.max(maxValue, left + right + node.val);
        //返回以当前节点为根的树的节点值之和。
        return Math.max(left, right) + node.val;
    }


    /**
     * LeetCode - 33
     * 搜素旋转排序数组 -时间复杂度O(logN)
     * 整数数组nums按升序排列,数组中的值互不相同
     *
     * 给你旋转后的数组nums和一个整数target,
     * 如果nums中存在这个目标值target,则返回它的下标。否正返回-1;
     * 输入:nums = [4,5,6,7,1,2,3],target = 0;
     * 输出:4
     */
    //二分查找
    public static int search(int[] nums, int target){
        int start = 0, end = nums.length - 1;
        while (start <= end){
            int mid = (start + end) / 2;
            int numMid = nums[mid];
            if(numMid == target){//找到了,直接返回
                return mid;
            }
            //numMid 和 target 不在同一段，将numMid变为正无穷或者负无穷
            if (!(numMid < nums[0] == target < nums[0])){
                numMid = target < nums[0] ? Integer.MIN_VALUE : Integer.MAX_VALUE;
            }
            //mid所指示的数num比target小,移动start,否则移动end
            if (numMid < target){
                start = mid + 1;
            }else {
                end = mid - 1;
            }
        }
        return -1;
    }


    /**
     * 在排序数组中查找元素的第一个和最后一个位置 O(lgn)
     *
     * 给定一个按照升序排列的整数数组nums,和一个目标值target,找出给定目标值在数组中的开始位置和结束位置。
     * 如果数组中不存在目标值返回[-1,-1]
     *
     * 1、简单的循环去寻找时间复杂O(N)
     * 2、二分查找时间复杂度O(lgn)
     */
    public int[] searchRange(int[] nums , int target){
        int[] result = new int[2];
        result[0] = findFirst(nums,target);
        if (result[0] == -1) return new int[]{-1,-1};
        result[1] = findLast(result[0], nums, target);
        return result;
    }
    public int findFirst(int[] nums, int target){
        int idx = -1;
        int start = 0;
        int end = nums.length -1;
        while (start <= end){
            int mid = (start + end) / 2;
            //等于的情况下也不能停止寻址,一定要找到start > end为止;
            if(nums[mid] >= target){
                end = mid - 1;
            }else {
                start = mid +1;
            }
            if(nums[mid] == target){
                idx = mid;
            }
        }
        return idx;
    }
    public int findLast(int first, int[] nums, int target){
        int idx = -1;
        int start = first;
        int ent = nums.length - 1;
        while (start <= ent){
            int mid = (start + ent) / 2;
            if (nums[mid] <= target){
                start = mid + 1;
            }else {
                ent = mid - 1;
            }
            if(nums[mid] == target){
                idx = mid;
            }
        }
        return idx;
    }

    /**
     * 深度优先
     *  二叉树的最小深度
     *      深度递归代码实现
     *
     */
    public static int minDepthDFS(TreeNode root){
        if (root == null){
            return 0;
        }
        if(root.left == null && root.right == null){
            return 1;
        }
        int min = Integer.MAX_VALUE;
        if(root.left != null){
            min = Math.min(maxDepth(root.left), min);
        }
        if(root.right != null){
            min = Math.min(maxDepth(root.right), min);
        }
        return min + 1;
    }

    /**
     * 广度遍历
     *  二叉树的最小深度
     */
    public static int minDepthBFS(TreeNode root){
        if (root == null){
            return 0;
        }
        Queue<TreeNode> queue = new LinkedList<TreeNode>();
        root.deep = 1;
        queue.offer(root);
        while (!queue.isEmpty()){
            //取出一个元素
            TreeNode node = queue.poll();
            //是一个叶子节点
            if(node.left == null && node.right == null){
                return node.deep;
            }
            if(node.left != null){
                node.left.deep = node.deep + 1;
                queue.offer(node.left);
            }
            if (node.right != null){
                node.right.deep = node.deep + 1;
                queue.offer(node.right);
            }
        }
        return 0;
    }



}

class TreeNode {
    int val;
    int deep;//代表节点的深度
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}